import lombok.Data;

/**
 * @author lzhphantom
 * @description
 * @date 创建于 20:09 2020/8/10
 * @modified
 */
public class AVLTree {
    private AVLNode root;

    public void add(int val) {
        if (this.root == null) {
            this.root = new AVLNode(1);
        }
    }

    public AVLNode findMinValue() {
        return this.root == null ? null : this.root.findMinValue();
    }

    public AVLNode findMaxValue() {
        return this.root == null ? null : this.root.findMaxValue();
    }

    public AVLNode find(int val) {
        return this.root == null ? null : this.root.find(val);
    }

    public void midOrder() {
        if (this.root == null) {
            return;
        }
        this.root.midOrder();
    }

    public AVLNode delete(int val) {
        return this.root == null ? null : this.root.delete(val);
    }
}

@Data
class AVLNode {
    private int val;
    private int times;
    private int height;
    private AVLNode left;
    private AVLNode right;

    public AVLNode(int val) {
        this.val = val;
        this.times = 1;
        this.height = 1;
    }

    public void updateHeight() {
        int leftHeight = this.left == null ? 0 : this.left.getHeight();
        int rightHeight = this.right == null ? 0 : this.right.getHeight();
        this.setHeight(Math.max(rightHeight, leftHeight));
    }

    public int balanceFactor() {
        int leftHeight = this.left == null ? 0 : this.left.getHeight();
        int rightHeight = this.right == null ? 0 : this.right.getHeight();
        return rightHeight - leftHeight;
    }

    public AVLNode rightRotation(AVLNode root) {
        AVLNode pivot = root.getLeft();
        AVLNode b = pivot.getRight();
        pivot.setRight(root);
        root.setLeft(b);

        root.updateHeight();
        pivot.updateHeight();
        return pivot;
    }

    public AVLNode leftRotation(AVLNode root) {
        AVLNode pivot = root.getRight();
        AVLNode b = pivot.getLeft();
        pivot.setLeft(root);
        root.setRight(b);

        root.updateHeight();
        pivot.updateHeight();
        return pivot;
    }

    public AVLNode leftRightRotation(AVLNode node) {
        node.setLeft(this.leftRotation(node.getLeft()));
        return this.rightRotation(node);
    }

    public AVLNode rightLeftRotation(AVLNode node) {
        node.setLeft(this.rightRotation(node.getRight()));
        return this.leftRotation(node);
    }

    public AVLNode add(int val) {
        if (this.val == val) {
            this.times++;
            return this;
        }
        AVLNode newNode = null;
        if (val > this.val) {
            this.right = this.right.add(val);
            int factor = this.balanceFactor();
            if (factor == -2) {
                if (val > this.right.getVal()) {
                    newNode = leftRotation(this);
                } else {
                    newNode = rightLeftRotation(this);
                }
            }
        } else {
            this.left = this.left.add(val);
            int factor = this.balanceFactor();
            if (factor == 2) {
                if (val < this.left.getVal()) {
                    newNode = rightRotation(this);
                } else {
                    newNode = leftRightRotation(this);
                }
            }
        }
        if (newNode == null) {
            this.updateHeight();
            return this;
        } else {
            newNode.updateHeight();
            return newNode;
        }
    }

    public AVLNode findMinValue() {
        return this.left == null ? this : this.left.findMinValue();
    }

    public AVLNode findMaxValue() {
        return this.right == null ? this : this.right.findMaxValue();
    }

    public AVLNode find(int val) {
        if (val == this.val) {
            return this;
        } else if (val < this.val) {
            return this.left == null ? null : this.left.find(val);
        } else {
            return this.right == null ? null : this.right.find(val);
        }
    }

    public void midOrder() {
        if (this.left != null) {
            this.left.midOrder();
        }
        for (int i = 0; i < this.times; i++) {
            System.out.printf("\t%d", this.val);
        }
        if (this.right != null) {
            this.right.midOrder();
        }
    }

    public AVLNode delete(int val) {
        if (val < this.val) {
            this.left = this.left.delete(val);
            this.left.updateHeight();
        } else if (val > this.val) {
            this.right = this.right.delete(val);
            this.right.updateHeight();
        } else {
            if (this.left == null && this.right == null) {
                return null;
            }
            if (this.left != null && this.right != null) {
                if (this.left.getHeight() > this.right.getHeight()) {
                    AVLNode maxNode = this.left;
                    while (maxNode.right != null) {
                        maxNode = maxNode.right;
                    }
                    this.val = maxNode.getVal();
                    this.times = maxNode.getTimes();

                    this.left = this.left.delete(maxNode.getVal());
                    this.left.updateHeight();
                } else {
                    AVLNode minNode = this.right;
                    while (minNode.left != null) {
                        minNode = minNode.left;
                    }
                    this.val = minNode.getVal();
                    this.times = minNode.getTimes();

                    this.right = this.right.delete(minNode.getVal());
                    this.right.updateHeight();
                }
            } else {
                if (this.left != null) {
                    this.val = this.left.getVal();
                    this.times = this.left.getTimes();
                    this.height = 1;
                    this.left = null;
                } else if (this.right != null) {
                    this.val = this.right.getVal();
                    this.times = this.right.getTimes();
                    this.height = 1;
                    this.right = null;
                }
            }
            return this;
        }

        AVLNode newNode = null;
        if (this.balanceFactor() == 2) {
            if (this.left.balanceFactor() >= 0) {
                newNode = rightRotation(this);
            } else {
                newNode = leftRightRotation(this);
            }
        } else if (this.balanceFactor() == -2) {
            if (this.right.balanceFactor() <= 0) {
                newNode = leftRotation(this);
            } else {
                newNode = rightLeftRotation(this);
            }
        }
        if (newNode == null) {
            this.updateHeight();
            return this;
        } else {
            newNode.updateHeight();
            return newNode;
        }
    }
}
